package com.leetcode.dfs;

public class MultiplyStrings {

    public static void main(String[] args) {
        String str1 = "123";
        String str2 = "456";
        MultiplyStrings multiplyStrings = new MultiplyStrings();
        String res = multiplyStrings.multiply(str1, str2);
        System.out.println(res);
    }

    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int len2 = num2.length();
        String str1 = charMulStr(num1, num2.charAt(len2 - 1));
        for (int i = len2 - 2; i >= 0; i--) {
            String str = charMulStr(num1, num2.charAt(i));
            for (int j = 0; j < len2 - 1 - i; j++) {
                str = str + "0";
            }
            str1 = strAddStr(str1, str);
        }

        return str1;
    }

    private String strAddStr(String str1, String str2) {
        int high = 0;
        int low = 0;
        String res = "";
        int len1 = str1.length();
        int len2 = str2.length();
        int maxLen = Math.max(len1, len2);
        int val1 = 0;
        int val2 = 0;
        for (int i = 0; i < maxLen; i++) {
            if (i < len1) {
                val1 = Integer.parseInt(String.valueOf(str1.charAt(len1 - i - 1)));
            } else {
                val1 = 0;
            }
            if (i < len2) {
                val2 = Integer.parseInt(String.valueOf(str2.charAt(len2 - i - 1)));
            } else {
                val2 = 0;
            }
            int tmp = val1 + val2 + high;
            if (tmp >= 10) {
                high = tmp / 10;
                low = tmp % 10;
            } else {
                high = 0;
                low = tmp;
            }
            res = low + res;
        }
        if (high != 0) {
            res = high + res;
        }
        return res;
    }

    private String charMulStr(String num1, char ch) {
        int high = 0;
        int low = 0;
        String res = "";
        for (int i = num1.length() - 1; i >= 0; i--) {
            int val1 = Integer.parseInt(String.valueOf(num1.charAt(i)));
            int val2 = Integer.parseInt(String.valueOf(ch));
            int tmp = val1 * val2 + high;
            if (tmp >= 10) {
                high = tmp / 10;
                low = tmp % 10;
            } else {
                high = 0;
                low = tmp;
            }
            res = low + res;
        }
        if (high != 0) {
            res = high + res;
        }
        return res;
    }
}
